#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long arr[51] = { 0 };
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i <= n; ++i) {
        arr[i] = (arr[i - 1] + arr[i - 2] + 2 * arr[i - 3]) % 10000;
    }
    cout << arr[n] % 10000 << endl;
    return 0;
}